package org.example.leetcode;
import java.util.*;
/**
 * @version 1.0.0
 * @author: lynn
 * @description: 电话号码的字母组合
 * @date: 2021/7/26 13:17
 */
public class LC17 {
    public static void main(String[] args) {
        LC17 lc=new LC17();
        System.out.println(lc.letterCombinations("23"));
    }
    private  static Map<Character,String> numsMap=new HashMap<>();
    static {
        numsMap.put('2',"abc");
        numsMap.put('3',"def");
        numsMap.put('4',"ghi");
        numsMap.put('5',"jkl");
        numsMap.put('6',"mno");
        numsMap.put('7',"pqrs");
        numsMap.put('8',"tuv");
        numsMap.put('9',"wxyz");
    }
    //fixme answer 执行过程: https://www.bilibili.com/video/BV1bv411h7oM?from=search&seid=12142378095081486455
    public List<String> letterCombinations(String digits) {
        List<String> res=new ArrayList<>();
        if (digits==null || digits.length()==0) return res;
        backTrack(res,numsMap,digits,0,new StringBuilder());
        return res;
    }
    private void backTrack(List<String> res,Map<Character,String> numsMap,String digits,int index,StringBuilder sb){
        if (index==digits.length()){
            res.add(sb.toString());
            return;
        }
        String letters=numsMap.get(digits.charAt(index));
        for (int i=0;i<letters.length();i++){
            sb.append(letters.charAt(i));
            backTrack(res,numsMap,digits,index+1,sb);
            sb.deleteCharAt(sb.length()-1);//fixme 这种就好理解了，就是把刚才加进去那个删了嘛
        }

    }
}
